package doublePointer;

import org.junit.Test;

/**
 * @author kunkun
 * @className LeetCode_42
 * @Description 接雨水问题
 * @date 2025/2/28 13:42
 */
public class LeetCode_42 {
    public int trap(int[] height) {
        return solution_3(height);
    }

    @Test
    public void test(){
        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(trap(new int[]{4,2,0,3,2,5}));
//        System.out.println(trap(new int[]{2,0,2}));
//        System.out.println(trap(new int[]{5,4,1,2}));
//        System.out.println(trap(new int[]{6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3}));
    }
    
    
    /**
    * @Description: 解法1：暴力求解，时间复杂度：O（n^2）
    * @Author: kunkun
    * @Date:  2025/2/28 13:43  
    * @Parameters: 
    * @Return 
    * @Throws 
    */
    public static int solution_1(int[] height){
        //1. 定义变量
        int result = 0;

        //2. 排除其它情况
        if (height.length==1){
            return result;
        }

        //3. 进入循环
        int l ,r;
        for (int i = 1; i < height.length-1; i++) {
            //3.1 定义l、r指针
            l = move(height,i,false);
            r = move(height,i,true);
            //3.2 条件判断，左边或者右边不存在更大的值（相邻）
            if (i==l||i==r){
                continue;
            }
            //3.3 计算雨水值
            int value = Math.min(height[l],height[r])-height[i];
            result+=(value>0)?value:0;
        }
        return result;
    }

    /**
     * 指针向两侧走，寻找最大位置
     * @param height
     * @param start
     * @return
     */
    public static int move(int[] height,int start,boolean forward){
        //1. 定义返回结果
        int index,maxIndex=start;
        //2. 遍历寻找最大位置
        if (forward){
            index = start+1;
            while(index<height.length){
                if (height[index]>height[maxIndex]){
                    maxIndex = index;
                }
                index++;
            }
        }else{
            index = start-1;
            while(index>=0){
                if (height[index]>height[maxIndex]){
                    maxIndex = index;
                }
                index--;
            }
        }
        return maxIndex;
    }

    /**
     * @Description: 解法2：利用前缀和求解，时间复杂度：
     * @Author: kunkun
     * @Date:  2025/2/28 13:43
     * @Parameters:
     * @Return
     * @Throws
     */
    public static int solution_2(int[] height){
        //1. 定义变量
        int result = 0;

        //2. 排除其它情况
        if (height.length==1){
            return result;
        }

        //3. 记录最大值、最小值
        int temp = 0;
        int[] max_l = new int[height.length];
        max_l[0]=temp;
        for (int i = 1; i < height.length; i++) {
            if (height[i]>=height[temp]){
                temp=i;
                max_l[i]=i;
            }else{
                max_l[i]=temp;
            }
        }
        temp = height.length-1;
        int[] max_r = new int[height.length];
        max_r[height.length-1]=temp;
        for (int i = height.length-2; i >= 0; i--) {
            if (height[i]>=height[temp]){
                temp=i;
                max_r[i]=i;
            }else{
                max_r[i]=temp;
            }
        }

        //3. 进入循环
        int l ,r;
        for (int i = 1; i < height.length-1; i++) {
            //3.1 定义l、r指针
            l = max_l[i];
            r = max_r[i];
            //3.2 条件判断，左边或者右边不存在更大的值（相邻）
            if (i==l||i==r){
                continue;
            }
            //3.3 计算雨水值
            int value = Math.min(height[l],height[r])-height[i];
            result+=(value>0)?value:0;
        }
        return result;
    }

    /**
     * @Description: 解法3：利用双指针求解，通过lMax和rMax记录左侧右侧最大值，同时移动指针，逐列判断
     * @Author: kunkun
     * @Date:  2025/2/28 13:43
     * @Parameters:
     * @Return
     * @Throws
     */
    public static int solution_3(int[] height){
        //1. 定义指针
        int l=0,lMax=height[l],r= height.length-1,rMax = height[r];
        int totalNum=0;

        //2. 循环遍历
        while (l<r){
            //2.1 判断
            if (lMax<=rMax){
                totalNum+=lMax-height[l];
                l++;
                lMax = (lMax>height[l])?lMax:height[l];
            }else{
                totalNum+=rMax-height[r];
                r--;
                rMax = (rMax>height[r])?rMax:height[r];
            }
        }
        return totalNum;

    }





}
